


class Solution:

    def solveNQueens(self, n):

        ans = []
        queens = [0] * n # 积分第几行分别放在哪个位置

        col = [False] * n

        diag1 = [False] * (n * 2 - 1)
        diag2 = [False] * (n * 2 - 1)

        def dfs(r):
            if r == n:
                ans.append(["." * c + 'Q' + "." * (n - 1 - c) for c in queens])
                return
            
            for c, ok in enumerate(col):
                if not ok and not diag1[r + c] and not diag2[r - c]:

                    queens[r] = c
                    col[c] = diag1[r + c] = diag2[r - c] = True
                    dfs(r + 1)
                    col[c] = diag1[r + c] = diag2[r - c] = False

        
        dfs(0)

        return ans
    

if __name__ == "__main__":

    n = 6
    sol = Solution()
    res = sol.solveNQueens(n)
    print(res)

